1. Technical Field
The present invention relates generally to compressed time-series representations and, more particularly, to systems and methods for computation of optimal distance bounds on compressed time-series data.
2. Description of the Related Art
In the data-mining community, searching on time-series data under the Euclidean metric has been studied extensively, as described by Agrawal et al., “Efficient Similarity Search in Sequence Databases”, in Proc. of Foundations of Data Organizations (FODO), 15 pages, 1993, Rafiei et al., “Efficient Retrieval of Similar Time Sequences Using dft”, in Proc. of Foundations of Data Organizations (FODO), 9 pages, November 1998, and Wang et al., “Multilevel Filtering for High Dimensional Nearest Neighbor Search”, in ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, pp. 1-7, 2000, the disclosures of which are incorporated by reference herein. However, such studies have typically considered compression using only the first Fourier or wavelets. The use of diverse sets of coefficients has been studied as described by Vlachos et al., “Identifying Similarities, Periodicities & Bursts for Online Search Queries”, in Proc. of SIGMOD, 12 pages, June 2004, the disclosure of which is incorporated by reference herein.
However, no prior art exists directed to the tightest possible lower/upper bounds.